package com.lwl.Algorithmic_data_structure.动态规划;

public class 最长公共回文子序列 {
    /**
     * 第一种方法可以直接反转字符串，然后求最长公共子序列（这样做看前面一题即可）
     */
    public int longestPalindromeSubseq(String s){
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[][] dp = new int[str.length][str.length];
        //设置边界条件，根据递归的baseCase设置
        int N = str.length;
        dp[N-1][N-1] = 1;
        for (int i = 0; i < N-1; i++) {
            dp[i][i] = 1;
            dp[i][i+1] = str[i] == str[i+1] ? 2 : 1;
        }
        for (int L = N-3; L >= 0; L--) {
            for (int R = L+2; R < N; R++) {
                dp[L][R] = Math.max(dp[L+1][R],dp[L][R-1]);
                if (str[L] == str[R]){
                    dp[L][R] = Math.max(dp[L][R],dp[L+1][R-1]+2);
                }
            }
        }
        return dp[0][N-1];
    }
    public int PalindromeSubsequence1(String s){
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        return process(str,0,str.length-1);
    }
    private int process(char[] str, int L, int R) {
        if (L == R){
            return str[L] == str[R] ? 1 : 0;
        }
        if (L + 1 == R){
            return str[L] == str[R] ? 2 : 1;
        }
        int p1 = process(str,L+1,R);//跳过L
        int p2 = process(str,L,R-1);//跳过R
        int p3 = process(str,L+1,R-1);//其实这一步没必要，因为前面两步的递归里肯定会包括这一步
        if (str[L] == str[R]){
            p3 += 2;
            return Math.max(Math.max(p1,p2),p3);
        }
        return Math.max(p1,p2);
    }
}
